#ifndef GRAPH_H_
#define GRAPH_H_
#include<climits>
#include<iostream>
#include<stack>
#include<list>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef enum {UNDISCOVERED,DISCOVERED,VISITED} VStatus;//status of vertexes
typedef enum {UNDETERMINED,TREE,CROSS,FORWARD,BACKWARD} EStatus;//status of edges
template<typename Tv> struct Vertex
{
    Tv data;int inDegree;int outDegree;VStatus status;
    int dTime,fTime;///tags to memorize when the vertexes are visited
    int parent;int priority;
    Vertex(Tv const& d=(Tv)0):data{d},inDegree{0},outDegree{0},status{UNDISCOVERED},
    dTime{-1},fTime{-1}{}
};

struct Edge
{
    int weight;EStatus status; ///index is specifically used in a list
    Edge(int w):weight{w},status{UNDETERMINED}{}
};

template<typename Tv>
class GraphMatrix//inplementation of a graph by a matrix consisting of vectors
{
    int n,e;
private:
    vector<Vertex<Tv>> V;     //vector container for vertexes 
    vector<vector<Edge*>> E;//two-dimensional vector container for edges
    vector<Tv> tag;
    void reset()
    {
        for(int i=0;i<n;i++)
        {
            status(i)=UNDISCOVERED;
            dTime(i)=fTime(i)=-1;
            priority(i)=INT_MAX;parent(i)=-1;
            for(int j=0;j<n;j++)
            {
                if(exists(i,j)) 
                    status(i,j)=UNDETERMINED;
            }
        }
    }
    int findElement(int key)   ///a function for finding an element and return the index
    {
	    int len = tag.size();
	    for(int i=0; i<len; i++)
        {
		    if(tag.at(i) == key){
			    return i;
		    }
	    }
	    return -1;
    }
public:
    GraphMatrix(){n=e=0;}///constructor
    ~GraphMatrix()///distructor
    {
        for(int j=0;j<n;j++)
        {
            E[j].clear();
        }
        E.clear();
    }
//basics operations for vertex i,where 0<=i<n
    Tv& vertex(int i){return V[i].data;}
    int& inDegree(int i){return V[i].inDegree;}
    int& outDegree(int i){return V[i].outDegree;}
    int& dTime(int i){return V[i].dTime;}
    int& fTime(int i){return V[i].fTime;}
    int firstNbr(int i){return nextNbr(i,n);}
    int& parent(int i){return V[i].parent;}
    int& priority(int i){return V[i].priority;}
    int nextNbr(int i,int j)
    {
        while((-1<j)&&(!exists(i,--j))); ///operation '--' preceeds because it starts 
        ///from n
            return j;
    }
    VStatus& status(int i){return V[i].status;}
//dynamic operations for vertex i,where 0<=i<n
    int insert(Tv const& vertex)
    {
        tag.push_back(vertex);
        for(int j=0;j<n;j++ )
            E[j].push_back(nullptr);
        n++;//prepare edges for every other vertexes
        E.push_back(vector<Edge*>(n,(Edge*)nullptr));//here a vector of n edges is constributed 
        V.push_back(Vertex<Tv>(vertex));//construct a Vertex(a struct) space for the new vertex and push it into
        return V.size();
    }
///basic static functions for edges
    bool exists(int i,int j)          ///judge the exitence of E[i][j]
    {return 0<=i&&i<n&&j<n&&E[i][j]!=nullptr&&i!=j;}
    EStatus& status(int i,int j){return E[i][j]->status;}
    /**
    *The function below is not added none-null condition because I don't want
    *to convert the returned value of a lvalue,so the limiting condition would
    *be exerted out of the function
    */
    int weight(int i,int j)
    { 
        if(exists(i,j)) 
            return E[i][j]->weight;
        return 0;
    }

///basic dynamic functions for edges
    void insert(int w,Tv a,Tv b)
    {
        int i=findElement(a);
        int j=findElement(b);
        if(exists(i,j)) return;
        if(i<0||i>=n||j<0||j>=n||i==j) return;
        E[i][j]=new Edge(w);
        e++;V[i].outDegree++;V[j].inDegree++;
    }
    void listVertexes()
    {
        for(int i=0;i<n;i++)
            cout<<V[i].data<<" ";
        cout<<endl;
    }
    void listEdges()
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<"i: "<<tag[i]<<" "<<"j "<<tag[j]<<" "<<"weitht: "<<weight(i,j)<<endl;
            }
            
        }
    }
///algorithms
private:
    void BFS(int v)            ///local search
    {
        queue<int> Q;
        status(v)=DISCOVERED;Q.push(v);
        while(!Q.empty())
        {
            v=Q.front();Q.pop();
            for(int u=firstNbr(v);u>-1;u=nextNbr(v,u))
                if(status(u)==UNDISCOVERED)
                {
                    status(u)=DISCOVERED;Q.push(u);
                    status(v,u)=TREE;
                }
                else
                {
                    status(v,u)=CROSS;
                }
            status(v)=VISITED;
        }
    }
    void DFS(int v,int& clock)
    {
        dTime(v)=++clock;
        status(v)=DISCOVERED;
        for(int u=firstNbr(v);u>-1;u=nextNbr(v,u))
            switch (status(u)){
                case UNDISCOVERED:
                    status(v,u)=TREE;DFS(u,clock);break;
                case DISCOVERED:
                    status(v,u)=BACKWARD;break;
                default:
                    status(v,u)=(dTime(v)<dTime(u))? FORWARD:CROSS;break;
            }
        status(v)=VISITED;fTime(v)=++clock;

    }
    bool TSort(int v,int &clock,stack<Tv>*S)
    {
        dTime(v)= ++clock;status(v)=DISCOVERED;
        for(int u=firstNbr(v);u>-1;u=nextNbr(v,u))
            switch(status(u))
            {
                case UNDISCOVERED:
                    status(v,u)=TREE;
                    if(!TSort(u,clock,S))
                        return false;
                    break;
                case DISCOVERED:
                    status(v,u)=BACKWARD;
                    return false;
                default:
                    status(v,u)=(dTime(v)<dTime(u)) ? FORWARD:CROSS;break;
            }
        status(v)=VISITED;S->push(vertex(v));
        return true;
    }
    template<typename PU> void PFS(int s,PU prioUpdater)
    {
        priority(s)=0;status(s)=VISITED;parent(s)=-1;
        while(1)
        {
            for(int w=firstNbr(s);w>-1;w=nextNbr(s,w))
                prioUpdater(this,s,w);
            for(int shortest=INT_MAX,w=0;w<n;w++)
            {
                if(status(w)=UNDISCOVERED)
                    if(shortest>priority(w))
                    {
                        shortest=priority(w);
                        s=w;
                    }
            }
            if(status(s)==VISITED) break;
            status(s)=VISITED;status(parent(s),s)=TREE;
        }
    }

public:
    void bfs()  /// complete search
    {
        reset();
        for(int i=0;i<n;i++)
        {
            if(status(i)==UNDISCOVERED)
                BFS(i);
        }
    }
    void dfs(Tv S)
    {
        int s=findElement(S);
        reset();int clock=0;
        DFS(s,clock);///the pointed vertex precedes
        for(int i=0;i<n;i++)
        {
            if(i==s)
                continue;
            if(status(i)==UNDISCOVERED)
                DFS(i,clock);
        }
    }
    stack<Tv>* tSort(Tv n)
    {
        int s=findElement(n);
        stack<Tv>* S=new stack<Tv>;
        reset();int clock=0;
        TSort(s,clock,S);
        for(int i=0;i<n;i++)
        {
            if(s==i)
                continue;
            if(status(i)==UNDISCOVERED)
            {
                if(!TSort(i,clock,S))
                {
                    while(!S->empty())
                        S->pop();
                    break;
                }
            }
        }
        return S;
    }
    template<typename PU> void pfs(Tv S,PU prioUpdater)
    {
        int s=findElement(S);
        reset();
        PFS(s,prioUpdater);
        for(int i=0;i<n;i++)
        {
            if(i==s)
                continue;
            if(status(i)==UNDISCOVERED)
                PFS(i,prioUpdater);
        }
        
    }

    void BellmanFord()
    {
		reset();
        priority(0)=0;///priority is regarded as distance
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(exists(i,j))///avoiding visiting inexistent edges
                {
                    if(priority(j)>priority(i)+weight(i,j))///loose
                    {
                        priority(j)=priority(i)+weight(i,j);
                        parent(j)=i;
                    }
                }
            }
        }
    	for(int i=0;i<n;i++)///adjust again
        {
            if(parent(i)!=-1)
            {
                if(priority(i)>priority(parent(i))+weight(parent(i),i))
                {    
                	priority(i)=priority(parent(i))+weight(parent(i),i);
                }
            }
        }
        for(int i=0;i<n;i++) ///pending whether negitive loops exists
        {
            if(parent(i)!=-1)
            {
                if(priority(i)>priority(parent(i))+weight(parent(i),i))
                {    
                	//cout<<"there exists a negtive loop";
                	//return;
                }
            }
        }
        /*for(int i=0;i<n;i++)///print the path and the shortest distance 
        {
        	if(parent(i)!=-1)
        	{
        		cout<<"the distance from "<<tag[0]<<" to "
				<<tag[i]<<" is "<<priority(i)<<endl;
			}
			/*cout<<"the path is ";
			int j=i;
            while(parent(j)!=-1)
            {
                cout<<tag[j]<<"<<";
                j=parent(j);
            }
            cout<<tag[0]<<endl;*/
		// }*

	}
};

template<typename Tv> struct PrimPU
{
    virtual void operator()(GraphMatrix<Tv>* g,int uk,int v)
    {
        if(g->status(v)==UNDISCOVERED)
            if(g->priority(v)>g->weight(uk,v))
            {
                g->priority(v)=g->weight(uk,v);
                g->parent(v)=uk;
            }
    }
};

#endif